package 图;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
/**
 * 二维 层面的   dfs 
 * 有点 小吊 了 
 * https://leetcode-cn.com/problems/pacific-atlantic-water-flow/solution/by-ac_oier-do7d/
 * 宫水三叶 提供了 三种解法 ：
 * 其中 有个 并查集    这个  还是 好好 理 解 一 下 
 * @author I adore you
 *
 */
public  class leetcode417太平洋大西洋问题 {
	
	   int dirs [][] = {{0,1},{0,-1},{1,0},{-1,0}};
	 	
	    List<List<Integer>> solution(int heights[][]){
		List<List<Integer>> ans = new ArrayList<>();
		int row = heights.length;
		int col = heights[0].length;
		int pArr[][] = new int [row][col]; // 记录 太平洋
		int oArr[][] = new int [row][col];// 记录 大西洋
		// 剪枝 用的  visited 这个  东西对吧
		boolean pFlag [][] = new boolean [row][col];
		boolean oFlag [][] = new boolean [row][col];
		for(int i = 0;i < row ;i++) {
			dfs(heights,pArr,pFlag,i,0);
			dfs(heights,oArr,oFlag,i,col - 1);
//			dfs(heights,pArr,pFlag,0,i);
//			dfs(heights,oArr,oFlag,col - 1,i);
		}
		for(int i = 0;i < col ;i++) {
			dfs(heights,pArr,pFlag,0,i);
			dfs(heights,oArr,oFlag,row - 1,i);
//			dfs(heights,pArr,pFlag,i,0);
//			dfs(heights,oArr,oFlag,i,row - 1);
		}
		for(int  i = 0;i < row ;i++) {
			for(int j = 0;j < col ;j++) {
				if(oArr[i][j] == 1 && pArr[i][j] == 1)
//					ans.add(new ArrayList<>(Arrays.asList(i,j)));
//					Arrays.asList(a);  这个 本身  返回 值 就是  return new ArrayList<>();
					ans.add(Arrays.asList(i,j));
			}
		}
//		System.out.println();
		/**
		 * 有错误  
		 * 
		 	1 1 
			1 1 
			
			0 1 
			1 1 
		 */
		for(int arr []: pArr) {
			for(int i : arr)
				System.out.print(i + " ");
			System.out.println();
		}
		for(int arr []: oArr) {
			for(int i : arr)
				System.out.print(i + " ");
			System.out.println();
		}
		for(boolean  arr [] :  pFlag) {
			for(boolean i : arr)
				System.out.print(i + " ");
			System.out.println();
		}
		for(boolean  arr [] :  oFlag) {
			for(boolean i : arr)
				System.out.print(i + " ");
			System.out.println();
		}
		return ans;
	}
	 void dfs(int heights[][],int record[][],boolean flag[][],int x,int y) {
		//basecase 
		 record[x][y] = 1;
		 flag[x][y] = true;
		 int temp = heights[x][y];
		 for(int dir[] : dirs) {
			 x += dir[0];
			 y += dir[1];
			 // flag[x][y] == true 代表 已经 走过 这就 跳过 
			 if(y >= heights[0].length || x >= heights.length || x < 0 || y < 0 || record[x][y] == 1  || heights[x][y] < temp) {
				 continue;
			 }
//			 if( flag[x][y]  ||x < 0 || x >= heights.length || y < 0 || y >= heights[0].length || heights[x][y] < temp) {
//				 continue;
//			 }
			 dfs(heights,record,flag,x,y);
		 }
		
	}
	
	 public static void main(String []args) {
		 int h[][] = {{2,1},{1,2}};
		 leetcode417太平洋大西洋问题 so = new leetcode417太平洋大西洋问题();
		 System.out.println(so.solution(h));
		 SolutionTwo s = new SolutionTwo();
		 System.out.println(s.pacificAtlantic(h));
	 }
}
class SolutionTwo {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        int[][] ao = new int[m][n];//太平洋的节点记录矩阵
        int[][] pa = new int[m][n];//大西洋的节点记录矩阵
        //1. 从上下边界开始两大洋的回流搜索，变动的是列
        for(int i=0;i<n;i++){
            dfs(heights,pa,0,i);
            dfs(heights,ao,m-1,i);
        }
        //2. 从左右边界开始两大洋的回流搜索，变动的是行
        for(int i=0;i<m;i++){
            dfs(heights,pa,i,0);
            dfs(heights,ao,i,n-1);
        }
        //3. 输出交叠的坐标
        List<List<Integer>> cnt = new ArrayList<List<Integer>>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(ao[i][j]==1&&pa[i][j]==1){
                    cnt.add(Arrays.asList(i,j));
                }
            }
        }
//        for(int i = 0;i < m;i++) {
//        	System.out.println(Arrays.toString(ao[i]));
//        	System.out.println(Arrays.toString(pa[i]));
//        }
        return cnt;
    }

    public static void dfs(int[][] heights,int[][] tmp,int cur_i,int cur_j){
        //标记可以从海洋流回经过的节点
        tmp[cur_i][cur_j]=1;
        //开始深度优先搜索当前坐标的4个方向
        //1. 设置更新的坐标
        int[] di=new int[]{1,-1,0,0};//上下移动
        int[] dj=new int[]{0,0,1,-1};//左右移动
        int new_i=0;
        int new_j=0;
        //2. 更新坐标并递归搜索
        for(int index=0;index<4;index++){
            new_i=cur_i+di[index];
            new_j=cur_j+dj[index];
            //判断下标是否越界
            if(new_i<0||new_j<0||new_i>=heights.length||new_j>=heights[0].length || tmp[new_i][new_j] == 1
            		|| heights[cur_i][cur_j] > heights[new_i][new_j]){
                continue;
            }
            dfs(heights,tmp,new_i,new_j);
//            if(heights[cur_i][cur_j]<=heights[new_i][new_j]){
//            }
        }
    }
}